package two;
import java.util.*;
class Node{
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
public class A032 {


    //随机链表的复制

    //题意：我们要复制一份链表出来，要求和给的Head一致
    //1.通过map，存储新节点和老节点的关系。遍历原链表，就相当于遍历新链表，但是此时新链表没有连接关系
    //2.再次遍历原链表，通过map也就是遍历新链表，然后给新的链表设置对应的关系。
    //新节点的next和random都要指向新的节点而不是老节点，所以需要通过map去寻找
    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        //1.存储新老链表的对应关系
        Node cur = head;
        while(cur!=null) {
            Node t = new Node(cur.val);
            map.put(cur,t);
            cur=cur.next;
        }
        //2.给新链表设置链接关系
        cur=head;
        while(cur!=null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}
